export default function getEditDistance(a, b) {
  let alen = a.length;
  let blen = b.length;
  const detail = []
  const arr = new Array((alen + 1) * (blen + 1));
  function geta(i, j) {
    return arr[j * (alen + 1) + i];
  }
  function seta(i, j, value) {
    arr[j * (alen + 1) + i] = value;
  }
  seta(0, 0, 0);
  for (let i = 1; i <= alen; i++)
    seta(i, 0, i);
  for (let i = 1; i <= blen; i++)
    seta(0, i, i);
  for (let j = 1; j <= blen; j++)
    for (let i = 1; i <= alen; i++) {
      const flag = a[i - 1] === b[j - 1]
      const m = (flag ? 0 : 1) + geta(i - 1, j - 1)
      const n = geta(i - 1, j) + 1
      const o = geta(i, j - 1) + 1
      if (m < n && m < o) {
        if (flag) {
          detail.push({
            type: 'match',
            lastIndex: [i - 1, j - 1],
            value: a[i - 1]
          })
        } else {
          detail.push({
            type: 'replace',
            from: a[i - 1],
            to: b[j - 1],
            lastIndex: [i - 1, j - 1],
          })
        }
        seta(i, j, m)
      } else {
        if (n < o) {
          detail.push({
            type: 'delete',
            lastIndex: [i - 1, j],
            value: a[i - 1],
          })
          seta(i, j, n)

        } else {
          detail.push({
            type: 'insert',
            lastIndex: [i, j - 1],
            value: b[j - 1],
          })
          seta(i, j, o)

        }
      }
    }
  let result = []
  let d = detail.slice(-1)[0]
  while (true) {
    const m = { ...d }
    delete m.lastIndex
    result.push(m)
    if (d.lastIndex[0] !== 0 && d.lastIndex[1] !== 0) {
      d = detail[(d.lastIndex[1] - 1) * alen + (d.lastIndex[0] - 1)]
    }
    else {
      if (d.lastIndex[0] === 0) {
        let t = d.lastIndex[1]
        while (t-- > 0) {
          result.push({
            type: 'insert',
            value: b[t]
          })
        }
      }
      if (d.lastIndex[1] === 0) {
        let t = d.lastIndex[0]
        while (t-- > 0) {
          result.push({
            type: 'delete',
            value: a[t]
          })
        }
      }
      break
    }
  }
  result = result.reverse()
  return {
    modifyCount: geta(alen, blen),
    count: result.length,
    result
  }
};

